/**
 * 
 */
package net.sf.graph4j.datastructure.disjointset.forest;

import net.sf.graph4j.element.AbstractNode;

/**
 * In a faster implementation of disjoint sets, we represent sets by rooted
 * trees, with each node containing one member and each tree representing one
 * set. In a disjoint-set forest, illustrated in Figure 21.4(a), each member
 * points only to its parent. The root of each tree contains the representative
 * and is its own parent. As we shall see, although the straightforward
 * algorithms that use this representation are no faster than ones that use the
 * linked-list representation, by introducing two heuristics-"union by rank" and
 * "path compression"-we can achieve the asymptotically fastest disjoint-set
 * data structure known.
 * 
 * @author chen cong
 * 
 */
public class DisjointSetNode2<E> extends AbstractNode<E> {

	private DisjointSetNode2<E> parent;

	/**
	 * To implement a disjoint-set forest with the union-by-rank heuristic, we
	 * must keep track of ranks. With each node x, we maintain the integer value
	 * rank[x], which is an upper bound on the height of x (the number of edges
	 * in the longest path between x and a descendant leaf). When a singleton
	 * set is created by MAKE-SET, the initial rank of the single node in the
	 * corresponding tree is 0. Each FIND-SET operation leaves all ranks
	 * unchanged. When applying UNION to two trees, there are two cases,
	 * depending on whether the roots have equal rank. If the roots have unequal
	 * rank, we make the root of higher rank the parent of the root of lower
	 * rank, but the ranks themselves remain unchanged. If, instead, the roots
	 * have equal ranks, we arbitrarily choose one of the roots as the parent
	 * and increment its rank.
	 */
	int rank;

	/**
	 * @param element
	 */
	public DisjointSetNode2(E element) {
		super(element);
		// TODO Auto-generated constructor stub
	}

	/**
	 * @return Returns the parent.
	 */
	public DisjointSetNode2<E> getParent() {
		return parent;
	}

	/**
	 * @param parent
	 *            The parent to set.
	 */
	public void setParent(DisjointSetNode2<E> parent) {
		this.parent = parent;
	}

	/**
	 * @return Returns the rank.
	 */
	public int getRank() {
		return rank;
	}

	/**
	 * @param rank
	 *            The rank to set.
	 */
	public void setRank(int rank) {
		this.rank = rank;
	}

}
